/LMAR=0/XLINE=3/FONT#0=BASL30/FONT#1=BASB30/FONT#2=ASI30[LSP,JRA]/FONT#3=SUB/FONT#4=ASI30[LSP,JRA]/FONT#5=BASB30/FONT#6=GRK30/FONT#7=SUP/FONT#8=SPEC[LSP,JRA]/FONT#9=SET1/FONT#10=GRFX25[LSP,JRA]/FONT#11=FIX30/FONT#12=NGB30/FONT#13=GERM35/FONT#14=MG[LSP,JRA]/FONT#15=GRFX35



␈↓ ↓H␈↓␈↓ ε	␈↓↓PREFACE␈↓


␈↓ ↓H␈↓␈↓ ∧λ"...␈α∞it␈α∂is␈α∞important␈α∂not␈α∞to␈α∞lose␈α∂sight␈α∞of␈α∂the␈α∞fact␈α∞that␈α∂there␈α∞is␈α∂a␈α∞difference
␈↓ ↓H␈↓␈↓ ∧λbetween␈α⊃training␈α⊃and␈α⊃education.␈α∩ If␈α⊃computer␈α⊃science␈α⊃is␈α∩a␈α⊃fundamental
␈↓ ↓H␈↓␈↓ ∧λdiscipline,␈α_then␈α↔university␈α_education␈α_in␈α↔this␈α_field␈α_should␈α↔emphasize
␈↓ ↓H␈↓␈↓ ∧λenduring fundamental principles rather than transient current technology."

␈↓ ↓H␈↓␈↓ ε]Peter Wegner, ␈↓αThree Computer Cultures␈↓[Weg 70] 

␈↓ ↓H␈↓This␈α∞text␈α∂is␈α∞nominally␈α∂about␈α∞LISP␈α∂and␈α∞data␈α∂structures.␈α∞However,␈α∂in␈α∞the␈α∂process␈α∞it␈α∂covers␈α∞much
␈↓ ↓H␈↓broader␈α∪areas␈α∪of␈α∩computer␈α∪science.␈α∪ The␈α∪author␈α∩has␈α∪long␈α∪felt␈α∩that␈α∪the␈α∪beginning␈α∪student␈α∩of
␈↓ ↓H␈↓computer␈αscience␈αhas␈αbeen␈αgetting␈αa␈αdistorted␈αand␈αdisjointed␈αpicture␈αof␈αthe␈αfield.␈αIn␈αsome␈αways␈αthis
␈↓ ↓H␈↓confusion␈α
is␈αnatural;␈α
the␈αfield␈α
has␈αbeen␈α
growing␈αat␈α
such␈αa␈α
rapid␈αrate␈α
that␈αfew␈α
are␈αprepared␈α
to␈αbe
␈↓ ↓H␈↓judged␈α∞experts␈α∞in␈α∞all␈α∞areas␈α∞of␈α∞the␈α∞discipline.␈α∂ The␈α∞current␈α∞alternative␈α∞seems␈α∞to␈α∞be␈α∞to␈α∞give␈α∂a␈α∞few
␈↓ ↓H␈↓introductory␈α
courses␈α∞in␈α
programming␈α∞and␈α
machine␈α
organization␈α∞followed␈α
by␈α∞relatively␈α
specialized
␈↓ ↓H␈↓courses␈α∞in␈α∞more␈α∞technical␈α∂areas.␈α∞The␈α∞difficulty␈α∞with␈α∞this␈α∂approach␈α∞is␈α∞that␈α∞much␈α∞of␈α∂the␈α∞technical
␈↓ ↓H␈↓material␈α
never␈α
gets␈α∞related.␈α
The␈α
student's␈α∞perspective␈α
and␈α
motivation␈α∞suffers␈α
in␈α
the␈α∞process.␈α
This
␈↓ ↓H␈↓book␈α⊂uses␈α⊃LISP␈α⊂as␈α⊃a␈α⊂means␈α⊃for␈α⊂relating␈α⊃topics␈α⊂which␈α⊃normally␈α⊂get␈α⊃treated␈α⊂in␈α⊃several␈α⊂separate
␈↓ ↓H␈↓courses.␈α
The␈α
point␈α
is␈α
not␈αthat␈α
we␈α
␈↓↓can␈↓␈α
do␈α
this␈αin␈α
LISP,␈α
but␈α
rather␈α
that␈α
it␈αis␈α
␈↓↓natural␈↓␈α
to␈α
do␈α
it␈αin␈α
LISP.
␈↓ ↓H␈↓The␈α⊃high-level␈α⊃notation␈α⊃for␈α⊃algorithms␈α⊃is␈α⊃beneficial␈α⊃in␈α⊃explaining␈α⊃and␈α⊃understanding␈α⊂complex
␈↓ ↓H␈↓algorithms.␈α∞ The␈α
use␈α∞of␈α
abstract␈α∞data␈α∞structures␈α
and␈α∞abstract␈α
LISP␈α∞programs␈α
shows␈α∞the␈α∞intent␈α
of
␈↓ ↓H␈↓structured␈α⊃programming␈α∩and␈α⊃step-wise␈α⊃refinement.␈α∩Much␈α⊃of␈α⊃the␈α∩current␈α⊃work␈α∩in␈α⊃mathematical
␈↓ ↓H␈↓theories␈αof␈αcomputation␈αis␈αbased␈αon␈αLISP-like␈αlanguages.␈αThus␈αLISP␈αis␈αa␈αformalism␈αfor␈αdescribing
␈↓ ↓H␈↓algorithms,␈αfor␈α
writing␈αprograms,␈αand␈α
for␈αproving␈α
properties␈αof␈αalgorithms.␈α
 We␈αuse␈αdata␈α
structures
␈↓ ↓H␈↓as␈αthe␈αmain␈αthread␈αin␈αour␈αdiscussions␈αbecause␈αa␈αproper␈αappreciation␈αof␈αdata␈αstructures␈α
as␈αabstract
␈↓ ↓H␈↓objects is a necessary prerequisite to an understanding of modern computer science.

␈↓ ↓H␈↓The␈α⊗importance␈α∃of␈α⊗abstraction␈α∃obviously␈α⊗goes␈α∃much␈α⊗further␈α∃than␈α⊗its␈α∃appearance␈α⊗in␈α∃LISP.
␈↓ ↓H␈↓Abstraction␈α⊂has␈α⊂often␈α⊂been␈α⊂used␈α⊂in␈α⊂other␈α⊂disciplines␈α⊂as␈α⊂a␈α⊂means␈α⊂for␈α⊂controlling␈α⊃complexity.␈α⊂In
␈↓ ↓H␈↓mathematics,␈α∞we␈α∞frequently␈α∞are␈α∞able␈α∞to␈α∞gain␈α∞new␈α∞insights␈α∞by␈α∞recasting␈α∞a␈α∂particularly␈α∞intransigent
␈↓ ↓H␈↓problem␈αin␈αa␈αmore␈αgeneral␈αsetting.␈α Similarly,␈αthe␈αintent␈αof␈αan␈αalgorithm␈αexpressed␈αin␈α
a␈αhigh-level
␈↓ ↓H␈↓language␈α⊂like␈α⊃Fortran␈α⊂or␈α⊃PL/1␈α⊂is␈α⊂more␈α⊃readily␈α⊂apparent␈α⊃than␈α⊂its␈α⊃machine-language␈α⊂equivalent.
␈↓ ↓H␈↓These␈α
are␈αboth␈α
examples␈αof␈α
the␈α
use␈αof␈α
abstraction.␈αOur␈α
use␈α
of␈αabstraction␈α
will␈αimpinge␈α
on␈αboth␈α
the
␈↓ ↓H␈↓mathematical␈αand␈αthe␈αprogramming␈αaspects.␈α Initially,␈αwe␈αwill␈αtalk␈αabout␈αdata␈αstructures␈αas␈αabstract
␈↓ ↓H␈↓objects␈αjust␈αas␈αthe␈αmathematician␈αtakes␈αthe␈αnatural␈αnumbers␈αas␈αabstract␈αentities.␈αWe␈αwill␈αattempt␈αto
␈↓ ↓H␈↓categorize␈α∂properties␈α∂common␈α⊂to␈α∂data␈α∂structures␈α∂and␈α⊂introduce␈α∂notation␈α∂for␈α⊂describing␈α∂functions
␈↓ ↓H␈↓defined␈αon␈α
these␈αabstractions.␈αAt␈α
this␈αlevel␈α
of␈αdiscussion␈αwe␈α
are␈αthinking␈α
of␈αour␈αLISP-like␈α
language
␈↓ ↓H␈↓primarily␈α
as␈αa␈α
notational␈α
convenience␈αrather␈α
than␈αa␈α
computational␈α
device.␈α However,␈α
after␈αa␈α
certain
␈↓ ↓H␈↓familiarity␈α
has␈αbeen␈α
established␈αit␈α
is␈αimportant␈α
to␈α
look␈αat␈α
our␈αwork␈α
from␈αthe␈α
viewpoint␈αof␈α
computer
␈↓ ↓H␈↓science.␈α
Here␈α
we␈α
must␈α
think␈α
of␈α
the␈α
computational␈α
aspects␈α
of␈α
our␈α
notation.␈α
We␈α
must␈α
be␈α
concerned
␈↓ ↓H␈↓with␈α⊗the␈α⊗representational␈α⊗problems:␈α⊗implementation␈α⊗on␈α⊗realistic␈α⊗machines,␈α⊗and␈α↔efficiency␈α⊗of
␈↓ ↓H␈↓algorithms␈α⊗and␈α⊗data␈α⊗structures.␈α⊗However,␈α⊗it␈α∃cannot␈α⊗be␈α⊗over-emphasized␈α⊗that␈α⊗our␈α⊗need␈α∃for
␈↓ ↓H␈↓understanding␈α⊃is␈α⊃best␈α⊂served␈α⊃at␈α⊃the␈α⊃higher␈α⊂level␈α⊃of␈α⊃abstraction;␈α⊂the␈α⊃advantage␈α⊃of␈α⊃a␈α⊂high-level
␈↓ ↓H␈↓language␈α
is␈αnotational␈α
rather␈αthan␈α
computational.␈αThat␈α
is,␈αit␈α
allows␈αus␈α
to␈αthink␈α
and␈α
represent␈αour



␈↓ ↓H␈↓algorithms␈α∂in␈α∂mathematical␈α∂terms␈α∂rather␈α∂than␈α∂in␈α⊂terms␈α∂of␈α∂the␈α∂machine.␈α∂ It␈α∂is␈α∂only␈α∂after␈α⊂a␈α∂clear
␈↓ ↓H␈↓understanding of the problem is attained that we should begin thinking about representation.

␈↓ ↓H␈↓We␈αcan␈α
exploit␈αthe␈αanalogy␈α
with␈αtraditional␈αmathematics␈α
a␈αbit␈αfurther.␈α
 When␈αwe␈αwrite␈α
␈↓αsqrt(x)␈↓␈αin
␈↓ ↓H␈↓Fortran,␈αfor␈αexample,␈αwe␈αare␈αinitially␈αonly␈αconcerned␈αwith␈α␈↓αsqrt␈↓␈αas␈αa␈αmathematical␈αfunction␈αdefined
␈↓ ↓H␈↓such␈α
that␈α
␈↓αx = sqrt(x)*sqrt(x)␈↓.␈α
We␈α
are␈α
not␈α
interested␈α
in␈α
the␈α
specific␈α
algorithm␈α
used␈α
to␈αapproximate
␈↓ ↓H␈↓the␈α∂function␈α∂intended␈α∂in␈α∂the␈α∂notation.␈α∂Indeed,␈α∞thought␈α∂of␈α∂as␈α∂a␈α∂mathematical␈α∂notation,␈α∂it␈α∞doesn't
␈↓ ↓H␈↓matter␈αhow␈α␈↓αsqrt␈↓␈αis␈αcomputed.␈αWe␈αmight␈αwish␈αto␈αprove␈αsome␈αproperties␈αof␈αthe␈αalgorithm␈α
which␈αwe
␈↓ ↓H␈↓are␈α∞encoding.␈α∞ If␈α∞so,␈α∞we␈α∞would␈α∞only␈α∞use␈α∞the␈α∞mathematical␈α∞properties␈α∞of␈α∞the␈α∞idealized␈α∞square␈α
root
␈↓ ↓H␈↓function.␈α
Only␈αlater,␈α
after␈αwe␈α
had␈αconvinced␈α
ourselves␈αof␈α
the␈αcorrect␈α
encoding␈αof␈α
our␈α
intention␈αin
␈↓ ↓H␈↓the␈α~Fortran␈α~program,␈α~would␈α→we␈α~worry␈α~about␈α~the␈α→computational␈α~aspects␈α~of␈α~the␈α→Fortran
␈↓ ↓H␈↓implementation␈α
␈↓αsqrt␈↓.␈α
The␈α
typical␈α
user␈α
will␈αnever␈α
proceed␈α
deeper␈α
into␈α
the␈α
representation␈α
than␈αthis;
␈↓ ↓H␈↓only␈α∪if␈α∩his␈α∪computation␈α∩is␈α∪lethargic␈α∩due␈α∪to␈α∩inefficiencies,␈α∪or␈α∩inaccurate␈α∪due␈α∪to␈α∩uncooperative
␈↓ ↓H␈↓approximations, will he look at the actual implementation of ␈↓αsqrt␈↓.

␈↓ ↓H␈↓Just␈α∩as␈α∩it␈α∩is␈α∩unnecessary␈α∩to␈α∩learn␈α⊃machine␈α∩language␈α∩to␈α∩study␈α∩numerical␈α∩algorithms,␈α∩it␈α∩is␈α⊃also
␈↓ ↓H␈↓unnecessary␈α∂to␈α∂learn␈α∞machine␈α∂language␈α∂to␈α∂understand␈α∞non-numerical␈α∂or␈α∂data␈α∂structure␈α∞processes.
␈↓ ↓H␈↓We␈α⊗make␈α⊗a␈α∃distinction␈α⊗between␈α⊗data␈α∃structures␈α⊗and␈α⊗storage␈α∃structures.␈α⊗Data␈α⊗structures␈α∃are
␈↓ ↓H␈↓abstractions,␈α∀independent␈α∃of␈α∀␈↓¬how␈↓␈α∃they␈α∀are␈α∀implemented␈α∃on␈α∀a␈α∃machine.␈α∀ Data␈α∃structures␈α∀are
␈↓ ↓H␈↓representations␈α⊂of␈α⊂information␈α⊃chosen␈α⊂to␈α⊂exhibit␈α⊃certain␈α⊂ordering␈α⊂and␈α⊃accessibility␈α⊂relationships
␈↓ ↓H␈↓between␈α∀data␈α∀items.␈α∃ Storage␈α∀structures␈α∀are␈α∀particular␈α∃implementations␈α∀of␈α∀the␈α∃abstract␈α∀ideas.
␈↓ ↓H␈↓Certainly␈αwe␈α
cannot␈αignore␈αstorage␈α
structures␈αwhen␈αwe␈α
are␈αdeciding␈αupon␈α
the␈αdata␈αstructures␈α
which
␈↓ ↓H␈↓will␈α
encode␈α
the␈α∞algorithm,␈α
but␈α
the␈α∞interesting␈α
aspects␈α
of␈α
the␈α∞representation␈α
of␈α
information␈α∞can␈α
be
␈↓ ↓H␈↓discussed␈αat␈αthe␈αlevel␈αof␈αdata␈αstructures␈αwith␈αno␈αloss␈αof␈αgenerality.␈α The␈αmapping␈αof␈αdata␈αstructures
␈↓ ↓H␈↓to␈αstorage␈αstructures␈αis␈α
usually␈αquite␈αmachine␈αdependent␈αand␈α
we␈αare␈αmore␈αinterested␈αin␈α
ideas␈αthan
␈↓ ↓H␈↓coding␈α
tricks.␈α
 We␈α
will␈α
see␈α
that␈α
it␈α
is␈αpossible,␈α
and␈α
most␈α
beneficial,␈α
to␈α
structure␈α
our␈α
programs␈αsuch
␈↓ ↓H␈↓that␈α
there␈α
is␈α
a␈α
very␈α
clean␈α
interface␈α
between␈α
the␈α
abstract␈α
algorithm␈α
and␈α
the␈α
chosen␈α
representation.
␈↓ ↓H␈↓That␈α⊂is,␈α⊂there␈α⊂will␈α⊃be␈α⊂a␈α⊂set␈α⊂of␈α⊂representation-manipulating␈α⊃programs␈α⊂to␈α⊂test,␈α⊂select␈α⊃or␈α⊂construct
␈↓ ↓H␈↓elements␈α∃of␈α∃the␈α∀domain;␈α∃and␈α∃there␈α∃will␈α∀be␈α∃a␈α∃program␈α∀encoding␈α∃the␈α∃algorithm.␈α∃To␈α∀change
␈↓ ↓H␈↓representations␈α⊃only␈α⊃requires␈α⊃changes␈α⊃to␈α∩constructors,␈α⊃selectors␈α⊃and␈α⊃predicates,␈α⊃not␈α⊃to␈α∩the␈α⊃basic
␈↓ ↓H␈↓program.

␈↓ ↓H␈↓One␈α∂important␈α∞insight␈α∂which␈α∞should␈α∂be␈α∂cultivated␈α∞in␈α∂this␈α∞process␈α∂is␈α∞the␈α∂distinction␈α∂between␈α∞the
␈↓ ↓H␈↓concepts␈α
of␈α
function␈α
and␈α
algorithm.␈α
 The␈α
idea␈α
of␈α
function␈α
is␈α
mathematical␈α
and␈α
is␈α
independent␈αof
␈↓ ↓H␈↓any␈αnotion␈αof␈αcomputation;␈αthe␈αmeaning␈αof␈α"algorithm"␈αis␈αcomputational,␈αthe␈αeffect␈αof␈αan␈αalgorithm
␈↓ ↓H␈↓being␈α⊃to␈α⊃compute␈α⊂a␈α⊃function.␈α⊃Thus␈α⊃there␈α⊂are␈α⊃typically␈α⊃many␈α⊂algorithms␈α⊃which␈α⊃will␈α⊃compute␈α⊂a
␈↓ ↓H␈↓specific function.

␈↓ ↓H␈↓This␈αtext␈αis␈α␈↓↓not␈↓␈αmeant␈αto␈αbe␈αa␈αprogramming␈αmanual␈αfor␈αLISP.␈α A␈αcertain␈αamount␈αof␈αtime␈αis␈αspent
␈↓ ↓H␈↓giving␈α
insights␈α
into␈α
techniques␈α
for␈α
writing␈α
LISP␈α
functions.␈α
 There␈α
are␈α
two␈α
reasons␈α
for␈α∞this.␈α
First,
␈↓ ↓H␈↓the␈α
style␈αof␈α
LISP␈α
programming␈αis␈α
quite␈α
different␈αfrom␈α
that␈α
of␈α"normal"␈α
programming.␈α
 LISP␈αwas
␈↓ ↓H␈↓one␈α
of␈α
the␈α
first␈α
languages␈α
to␈α
exploit␈αthe␈α
virtues␈α
of␈α
recursive␈α
programming␈α
and␈α
explore␈α
the␈αpower␈α
of
␈↓ ↓H␈↓procedure-valued␈αvariables.␈α Second,␈αwe␈αwill␈αspend␈αa␈αgreat␈αdeal␈αof␈αtime␈αdiscussing␈αvarious␈αlevels␈α
of
␈↓ ↓H␈↓implementation␈αof␈αthe␈αlanguage.␈αLISP␈αis␈αan␈αexcellent␈αmedium␈αfor␈αintroducing␈αstandard␈αtechniques
␈↓ ↓H␈↓in␈α⊂data␈α⊂structure␈α⊂manipulation.␈α⊃Techniques␈α⊂for␈α⊂implementation␈α⊂of␈α⊂recursion,␈α⊃implementation␈α⊂of



␈↓ ↓H␈↓complex␈αdata␈α
structures,␈αstorage␈α
management,␈αand␈α
symbol␈αtable␈α
manipulation␈αare␈α
easily␈αmotivated
␈↓ ↓H␈↓in␈α∞the␈α∞context␈α∞of␈α∞language␈α∞implementation.␈α∞Many␈α
of␈α∞these␈α∞standard␈α∞techniques␈α∞first␈α∞arose␈α∞in␈α
the
␈↓ ↓H␈↓implementation␈α∞of␈α∞LISP.␈α∞But␈α∞it␈α∞is␈α∞pointless␈α∞to␈α∞attempt␈α∞a␈α∞discussion␈α∞of␈α∞implementation␈α∞unless␈α
the
␈↓ ↓H␈↓reader has a thorough grasp of the language.

␈↓ ↓H␈↓Granting␈α∂the␈α∞efficacy␈α∂of␈α∞our␈α∂endeavor␈α∞in␈α∂abstraction,␈α∞why␈α∂study␈α∞LISP?␈α∂ LISP␈α∞is␈α∂at␈α∂least␈α∞fifteen
␈↓ ↓H␈↓years␈α⊃old␈α⊂and␈α⊃many␈α⊂languages␈α⊃new␈α⊂languages␈α⊃have␈α⊂been␈α⊃proposed.␈α⊂ The␈α⊃difficulty␈α⊂is␈α⊃that␈α⊂the
␈↓ ↓H␈↓appropriate␈α
combination␈α
of␈αthese␈α
features␈α
is␈α
not␈αpresent␈α
in␈α
any␈αother␈α
language.␈α
LISP␈α
unifies␈αand
␈↓ ↓H␈↓rationalizes␈α∞many␈α∞divergent␈α∞formulations␈α∞of␈α∞language␈α∞constructs.␈α∞ One␈α∞might␈α∞surmise␈α∞that␈α∞a␈α∞new
␈↓ ↓H␈↓language,␈αprofiting␈αfrom␈αLISP's␈αexperience,␈α
would␈αmake␈αa␈αbetter␈αpedagogical␈αtool.␈α
 Toy␈αlanguages
␈↓ ↓H␈↓are␈α∞suspect␈α∞for␈α
several␈α∞reasons.␈α∞The␈α
student␈α∞may␈α∞suspect␈α
that␈α∞he␈α∞is␈α
a␈α∞subject␈α∞in␈α
a␈α∞not␈α∞too␈α
clever
␈↓ ↓H␈↓experiment␈α⊂being␈α⊂performed␈α⊂upon␈α∂him␈α⊂by␈α⊂his␈α⊂instructor.␈α⊂Having␈α∂a␈α⊂backlog␈α⊂of␈α⊂fifteen␈α⊂years␈α∂of
␈↓ ↓H␈↓experience␈αand␈α
example␈αprograms␈αshould␈α
do␈αmuch␈αto␈α
alleviate␈αthis␈αdiscomfort.␈α
 The␈αdevelopment
␈↓ ↓H␈↓of␈αLISP␈αalso␈αshows␈αmany␈αof␈αthe␈αmistakes␈αthat␈αthe␈αoriginal␈αimplementors␈αand␈αdesigners␈αmade.␈α We
␈↓ ↓H␈↓will point out the flaws and pitfalls awaiting the unwary language designer.

␈↓ ↓H␈↓We␈α⊂claim␈α∂the␈α⊂more␈α∂interesting␈α⊂aspects␈α∂of␈α⊂LISP␈α∂for␈α⊂students␈α∂of␈α⊂Computer␈α∂Science␈α⊂lie␈α∂not␈α⊂in␈α∂its
␈↓ ↓H␈↓features␈α∞as␈α∞a␈α∞programming␈α∞language,␈α∞but␈α∞in␈α∂what␈α∞it␈α∞can␈α∞show␈α∞about␈α∞the␈α∞␈↓↓structure␈↓␈α∂of␈α∞Computer
␈↓ ↓H␈↓Science.␈α∞ There␈α∂is␈α∞a␈α∞rapidly␈α∂expanding␈α∞body␈α∂of␈α∞knowledge␈α∞unique␈α∂to␈α∞Computer␈α∂Science,␈α∞neither
␈↓ ↓H␈↓mathematical␈α⊂nor␈α⊂engineering␈α⊂per␈α⊂se.␈α⊂ Much␈α⊂of␈α∂this␈α⊂area␈α⊂is␈α⊂presented␈α⊂most␈α⊂clearly␈α⊂by␈α∂studying
␈↓ ↓H␈↓LISP.

␈↓ ↓H␈↓Again␈αthere␈αare␈αtwo␈αways␈αto␈αlook␈αat␈αa␈αhigh␈αlevel␈αlanguage:␈αas␈αa␈αmathematical␈αformalism,␈αand␈αas␈αa
␈↓ ↓H␈↓programming␈α
language.␈α
 LISP␈α
is␈α
a␈α
better␈α∞formalism␈α
than␈α
most␈α
of␈α
its␈α
mathematical␈α∞rivals␈α
because
␈↓ ↓H␈↓there␈α∞is␈α∞sufficient␈α∞organizational␈α∞complexity␈α∞present␈α∞in␈α∞LISP␈α∞so␈α∞as␈α∞to␈α∞make␈α∞its␈α∂implementation␈α∞a
␈↓ ↓H␈↓realistic␈α∂computer␈α⊂science␈α∂task␈α∂and␈α⊂not␈α∂just␈α⊂an␈α∂interesting␈α∂mathematical␈α⊂curiosity.␈α∂ Much␈α⊂of␈α∂the
␈↓ ↓H␈↓power␈α∩of␈α∩LISP␈α∩lies␈α∪in␈α∩its␈α∩simplicity.␈α∩ The␈α∩data␈α∪structures␈α∩are␈α∩rich␈α∩enough␈α∩to␈α∪easily␈α∩describe
␈↓ ↓H␈↓sophisticated␈α∩algorithms␈α∩but␈α∩not␈α∩so␈α∩rich␈α∩as␈α⊃to␈α∩become␈α∩obfuscatory.␈α∩ Most␈α∩every␈α∩aspect␈α∩of␈α⊃the
␈↓ ↓H␈↓implementation␈α∞of␈α∞LISP␈α∞and␈α∞its␈α∂translators␈α∞has␈α∞immediate␈α∞implications␈α∞to␈α∞the␈α∂implementation␈α∞of
␈↓ ↓H␈↓other languages and to the design of programming languages in general.

␈↓ ↓H␈↓We␈α
will␈αdescribe␈α
language␈α
translators␈α(interpreters␈α
and␈α
compilers)␈αas␈α
LISP␈α
functions.␈α The␈α
structure
␈↓ ↓H␈↓of␈αthese␈αtranslators␈αwhen␈αexposed␈αas␈αLISP␈αfunctions␈αaids␈αimmensely␈αin␈αunderstanding␈αthe␈αessential
␈↓ ↓H␈↓character␈α∂of␈α∂such␈α∂translators.␈α∂ This␈α∞is␈α∂partly␈α∂due␈α∂to␈α∂the␈α∞simplicity␈α∂of␈α∂the␈α∂language,␈α∂but␈α∞perhaps
␈↓ ↓H␈↓more␈αdue␈αto␈αour␈αability␈αto␈αgo␈αright␈αto␈αthe␈αessential␈αtranslating␈αalgorithm␈αwithout␈αbecoming␈αbogged
␈↓ ↓H␈↓down in details of syntax.

␈↓ ↓H␈↓LISP␈αhas␈αvery␈αimportant␈αimplications␈αin␈α
the␈αfield␈αof␈αprogramming␈αlanguage␈αsemantics,␈αand␈α
is␈αthe
␈↓ ↓H␈↓dominant␈αlanguage␈αin␈αthe␈αclosely␈αrelated␈αstudy␈αof␈αprovability␈αof␈αproperties␈αof␈αprograms.␈α The␈αidea
␈↓ ↓H␈↓of␈α⊃proving␈α⊃properties␈α⊂of␈α⊃programs␈α⊃has␈α⊂been␈α⊃around␈α⊃for␈α⊂a␈α⊃very␈α⊃long␈α⊂time.␈α⊃Goldstine␈α⊃and␈α⊂von
␈↓ ↓H␈↓Neumann␈αwere␈αaware␈αof␈αthe␈αpractical␈αbenefits␈α
of␈αsuch␈αendeavors.␈αJ.␈αMcCarthy's␈αwork␈αin␈αLISP␈α
and
␈↓ ↓H␈↓the␈α∂Theory␈α∂of␈α∞Computation␈α∂sought␈α∂to␈α∞establish␈α∂formalisms␈α∂and␈α∞rules␈α∂of␈α∂inference␈α∂for␈α∞reasoning
␈↓ ↓H␈↓about␈α
programs.␈α
 However,␈α
the␈α
working␈α
programmers␈αrecognized␈α
debugging␈α
as␈α
the␈α
only␈α
tool␈αwith
␈↓ ↓H␈↓which␈α
to␈α
generate␈α
a␈α
"correct"␈α
program,␈α
though␈αclearly␈α
the␈α
non-occurrence␈α
of␈α
bugs␈α
is␈α
no␈αguarantee␈α
of
␈↓ ↓H␈↓correctness.␈α Until␈αvery␈αrecently␈αtechniques␈αfor␈αestablishing␈αcorrectness␈αof␈αpractical␈αprograms␈α
simply
␈↓ ↓H␈↓did not exist.



␈↓ ↓H␈↓A recent set of events is beginning to change this.

␈↓ ↓H␈↓␈↓ ↓x␈↓↓1.␈↓␈α∂Programs␈α∂are␈α∂becoming␈α∂so␈α∂large␈α∂and␈α∞complex␈α∂that,␈α∂even␈α∂though␈α∂we␈α∂write␈α∂in␈α∂a␈α∞high-level
␈↓ ↓H␈↓␈↓ ↓xlanguage,␈α⊂our␈α⊂intuitions␈α⊂are␈α⊂not␈α⊂sufficient␈α⊂to␈α⊂sustain␈α∂us␈α⊂when␈α⊂we␈α⊂try␈α⊂to␈α⊂find␈α⊂bugs.␈α⊂We␈α∂are
␈↓ ↓H␈↓␈↓ ↓xliterally being forced to look beyond debugging.

␈↓ ↓H␈↓␈↓ ↓x␈↓↓2.␈↓␈α
The␈α
formalisms␈α
are␈α
maturing.␈α
We␈α
know␈αa␈α
lot␈α
more␈α
about␈α
how␈α
to␈α
write␈α"structured␈α
programs";
␈↓ ↓H␈↓␈↓ ↓xwe␈α∂know␈α∂how␈α∂to␈α∂design␈α∂languages␈α∂whose␈α∂constructs␈α∂are␈α∂more␈α∂amenable␈α∂to␈α∂proof␈α∞techniques.
␈↓ ↓H␈↓␈↓ ↓xAnd␈α
most␈α
importantly,␈α
the␈αtools␈α
we␈α
need␈α
for␈α
expressing␈αproperties␈α
of␈α
programs␈α
are␈αfinally␈α
being
␈↓ ↓H␈↓␈↓ ↓xdeveloped.

␈↓ ↓H␈↓␈↓ ↓x␈↓↓3.␈↓␈α∂The␈α∂development␈α∂of␈α∂on-line␈α⊂techniques.␈α∂The␈α∂on-line␈α∂system,␈α∂with␈α∂its␈α⊂sophisticated␈α∂display
␈↓ ↓H␈↓␈↓ ↓xeditors,␈α⊗debuggers␈α⊗and␈α↔file␈α⊗handlers,␈α⊗is␈α↔the␈α⊗only␈α⊗reason␈α↔that␈α⊗the␈α⊗traditional␈α↔means␈α⊗of
␈↓ ↓H␈↓␈↓ ↓xconstruction␈α
and␈αmodification␈α
of␈αcomplex␈α
programs␈αand␈α
systems␈αhas␈α
been␈αable␈α
to␈α
survive␈αthis
␈↓ ↓H␈↓␈↓ ↓xlong.

␈↓ ↓H␈↓This␈αview␈αof␈αthe␈αprogramming␈αprocess␈αblends␈αwell␈αwith␈αthe␈αLISP␈αphilosophy.␈α We␈αwill␈α
show␈αthat
␈↓ ↓H␈↓the␈α
most␈α
natural␈α
way␈αto␈α
write␈α
LISP␈α
programs␈αis␈α
"structured"␈α
in␈α
the␈αbest␈α
sense␈α
of␈α
the␈α
word,␈αbeing
␈↓ ↓H␈↓clean␈α∪in␈α∪control␈α∩structure,␈α∪concise␈α∪by␈α∩not␈α∪attempting␈α∪to␈α∩do␈α∪too␈α∪much,␈α∩and␈α∪independent␈α∪of␈α∩a
␈↓ ↓H␈↓particular data representation.

␈↓ ↓H␈↓Many␈α
of␈α
the␈α
existing␈α
techniques␈α
for␈α
establishing␈α
correctness␈α
originated␈α
in␈αMcCarthy's␈α
investigations
␈↓ ↓H␈↓of␈αLISP;␈αand␈αsome␈αvery␈αrecent␈αwork␈αon␈αmathematical␈αmodels␈αfor␈αprogramming␈αlanguages␈αis␈αeasily
␈↓ ↓H␈↓motivated from a discussion of LISP.

␈↓ ↓H␈↓Finally␈αthere␈αare␈αcertain␈αproperties␈αof␈αLISP-like␈αlanguages␈αwhich␈αmake␈αthem␈αthe␈αnatural␈αcandidate
␈↓ ↓H␈↓for␈αinteractive␈αprogram␈α
specification.␈α In␈αthe␈α
chapter␈αon␈αimplications␈α
of␈αLISP␈αwe␈α
will␈αcharacterize
␈↓ ↓H␈↓"LISP-like" and show how interactive methods can be developed.

␈↓ ↓H␈↓This␈α∞text␈α∞is␈α
primarily␈α∞designed␈α∞for␈α
undergraduates␈α∞and␈α∞therefore␈α
an␈α∞attempt␈α∞is␈α
made␈α∞to␈α∞make␈α
it
␈↓ ↓H␈↓self-contained.␈αThere␈αare␈αbasically␈αfive␈αareas␈αin␈αwhich␈αto␈αpartition␈αthe␈αtopics:␈αthe␈αmechanics␈αof␈αthe
␈↓ ↓H␈↓language,␈αthe␈αevaluation␈αof␈α
expressions␈αin␈αLISP,␈αthe␈αstatic␈α
structure␈αof␈αLISP,␈αthe␈αdynamic␈α
structure
␈↓ ↓H␈↓of␈α
LISP,␈α
and␈α
the␈α
efficient␈α
representation␈α∞of␈α
data␈α
structures␈α
and␈α
algorithms.␈α
 Each␈α
area␈α∞builds␈α
on
␈↓ ↓H␈↓the␈α
previous.␈α
Taken␈αas␈α
a␈α
group␈α
these␈αtopics␈α
introduce␈α
much␈α
of␈αwhat␈α
is␈α
interesting␈αcomputer␈α
science.
␈↓ ↓H␈↓The␈α∩first␈α∩area␈α∩develops␈α∪the␈α∩programming␈α∩philosophy␈α∩of␈α∩LISP:␈α∪the␈α∩use␈α∩of␈α∩data␈α∪structures␈α∩in
␈↓ ↓H␈↓programming;␈α
the␈α∞language␈α
constructs␈α
of␈α∞recursion;␈α
and␈α
other␈α∞uncommon␈α
control␈α∞structures.␈α
 The
␈↓ ↓H␈↓second␈α
area␈αinvolves␈α
a␈α
careful␈αstudy␈α
of␈αthe␈α
meaning␈α
of␈αevaluation␈α
in␈α
LISP␈αgives␈α
insights␈αinto␈α
other
␈↓ ↓H␈↓languages␈α∞and␈α∞to␈α∞the␈α∞general␈α∞question␈α∞of␈α
implementation.␈α∞The␈α∞next␈α∞two␈α∞areas␈α∞are␈α∞involved␈α
with
␈↓ ↓H␈↓implementation.␈α
The␈αsection␈α
on␈αstatic␈α
structure␈αdeals␈α
with␈αthe␈α
basic␈αorganization␈α
of␈αmemory␈α
for␈αa
␈↓ ↓H␈↓LISP␈α⊂machine -- be␈α∂it␈α⊂hardware␈α⊂or␈α∂simulated␈α⊂in␈α∂software.␈α⊂The␈α⊂dynamics␈α∂of␈α⊂LISP␈α⊂discusses␈α∂the
␈↓ ↓H␈↓primitive␈α∀control␈α∀structures␈α∪necessary␈α∀for␈α∀implementation␈α∀of␈α∪the␈α∀LISP␈α∀control␈α∀structures␈α∪and
␈↓ ↓H␈↓procedure␈α
calls.␈α
LISP␈α
compilers␈α
are␈α
discussed␈α
here.␈α
 The␈α
final␈α
section␈α
relates␈α
our␈α
discussion␈αof␈α
LISP
␈↓ ↓H␈↓and␈αits␈αimplementation␈αto␈αthe␈αmore␈αtraditional␈αmaterial␈αof␈αa␈αdata␈αstructures␈αcourse.␈αWe␈αdiscuss␈αthe
␈↓ ↓H␈↓problems␈α∂of␈α∂efficient␈α∂representation␈α∂of␈α∂data␈α∂structures.␈α∂By␈α∂this␈α∂point␈α∂the␈α∂student␈α∂should␈α∂have␈α∞a
␈↓ ↓H␈↓better␈α⊂understanding␈α⊂of␈α⊂the␈α⊂uses␈α⊂of␈α⊂data␈α⊂structures␈α⊂and␈α⊂should␈α⊂be␈α⊂motivated␈α⊂to␈α⊃examine␈α⊂these
␈↓ ↓H␈↓issues.



␈↓ ↓H␈↓A␈α
large␈αcollection␈α
of␈αproblems␈α
has␈αbeen␈α
included.␈αThe␈α
reader␈αis␈α
urged␈αto␈α
do␈αas␈α
many␈α
as␈αpossible.
␈↓ ↓H␈↓The␈αproblems␈α
are␈αmostly␈α
non-trivial;␈αthey␈α
attempt␈αto␈α
be␈αrealistic,␈α
introducing␈αsome␈αnew␈α
information
␈↓ ↓H␈↓which␈α
the␈α
readers␈α
should␈α∞be␈α
able␈α
to␈α
discover␈α
themselves.␈α∞There␈α
are␈α
also␈α
a␈α
few␈α∞rather␈α
substantial
␈↓ ↓H␈↓projects.␈α At␈αleast␈α
one␈αshould␈αbe␈αattempted.␈α
 There␈αis␈αa␈αsignificant␈α
difference␈αbetween␈αbeing␈αable␈α
to
␈↓ ↓H␈↓program small problems and being able to handle large projects.

␈↓ ↓H␈↓The␈αtext␈αis␈αlarge␈αand␈αcovers␈αmuch␈αmore␈αthan␈αis␈αrecommended␈αfor␈αa␈αone-semester␈αcourse.␈αA␈αtypical
␈↓ ↓H␈↓one semester course on data structures covers:
␈↓ ↓H␈↓␈↓ β8Chapter 1: all
␈↓ ↓H␈↓␈↓ β8Chapter 2: without 2.4 and 2.9.
␈↓ ↓H␈↓␈↓ β8Chapter 3: without 3.12, and mathematical aspects of 3.13
␈↓ ↓H␈↓␈↓ β8Chapter 4: without 4.7, 4.8, and the mathematical aspects of 4.11
␈↓ ↓H␈↓␈↓ β8Chapter 5: without 5.8, 5.19, and 5.20
␈↓ ↓H␈↓␈↓ β8Chapter 6: without 6.8, 6.9, 6.12 through 6.19
␈↓ ↓H␈↓␈↓ β8Chapter 7: without 7.4, 7.5, 7.10 through 7.13
␈↓ ↓H␈↓␈↓ β8Chapter 8 is also optional.

␈↓ ↓H␈↓If␈α∞a␈α
good␈α∞interactive␈α∞LISP␈α
implementation␈α∞is␈α
available,␈α∞then␈α∞the␈α
pace␈α∞can␈α
be␈α∞quickened␈α∞and␈α
the
␈↓ ↓H␈↓projects␈α⊃enlarged.␈α⊂ However,␈α⊃if␈α⊂only␈α⊃a␈α⊂poor␈α⊃or␈α⊂mediocre␈α⊃implementation␈α⊂is␈α⊃accessible,␈α⊃then␈α⊂the
␈↓ ↓H␈↓course␈α⊃time␈α⊃is␈α⊃better␈α⊃spent␈α⊃without␈α⊃␈↓↓any␈↓␈α⊃actual␈α⊃programming.␈α⊃LISP␈α⊃is␈α⊃an␈α⊃interactive␈α⊂language;
␈↓ ↓H␈↓attempts at other modes of operation do a disservice to both the language and the user.

␈↓ ↓H␈↓Finally␈α∞a␈α
note␈α∞on␈α
the␈α∞structure␈α
of␈α∞the␈α
text.␈α∞The␈α
emphasis␈α∞flows␈α
from␈α∞the␈α
abstract␈α∞to␈α∞the␈α
specific,
␈↓ ↓H␈↓beginning␈αwith␈α
a␈αprecise␈αdescription␈α
of␈αthe␈αdomain␈α
of␈αLISP␈αfunctions␈α
and␈αthe␈α
operations␈αdefined
␈↓ ↓H␈↓over␈αthat␈αdomain,␈αand␈αmoves␈α
to␈αa␈αdiscussion␈αof␈αthe␈α
details␈αof␈αefficient␈αimplementation␈αof␈α
LISP-like
␈↓ ↓H␈↓languages.␈α The␈αpractical-minded␈αprogrammer␈αmight␈αbe␈αput-off␈αby␈αthe␈α"irrelevant"␈αtheory␈αand␈αthe
␈↓ ↓H␈↓theoretical-minded␈αmathematician␈αmight␈αbe␈αput-off␈αby␈αthe␈α"irrelevant"␈αdetails␈αof␈αimplementation.␈αIf
␈↓ ↓H␈↓you lie somewhere between these two extremes, then welcome.



␈↓ ↓H␈↓␈↓ ¬SBIBLIOGRAPHY




␈↓ ↓H␈↓The basic form of an entry consists of three items:

␈↓ ↓H␈↓␈↓ α_␈↓↓1.␈↓ A short name which is how the document is referenced in the text.

␈↓ ↓H␈↓␈↓ α_␈↓↓2.␈↓ The full bibliographical reference.

␈↓ ↓H␈↓␈↓ α_␈↓↓3.␈↓␈α∂A␈α∂sequence␈α⊂of␈α∂pages␈α∂in␈α⊂the␈α∂text␈α∂which␈α∂refer␈α⊂to␈α∂this␈α∂document.␈α⊂If␈α∂the␈α∂document␈α⊂is␈α∂not
␈↓ ↓H␈↓␈↓ α_referenced␈α∂the␈α∂statement␈α∂␈↓↓[ norefs ]␈↓␈α∂appears␈α∞instead;␈α∂these␈α∂documents,␈α∂while␈α∂not␈α∞referenced,
␈↓ ↓H␈↓␈↓ α_are relevant to the material covered in the text.

␈↓ ↓H␈↓[Weg 70]␈↓ αx1 ␈↓↓[␈↓



␈↓ ↓H␈↓↓␈↓ ∧ZT A B L E   O F   C O N T E N T S



␈↓ ↓H␈↓↓CHAPTER␈↓ ¬PAGE␈↓


␈↓ ↓H␈↓␈↓ ↓xBIBLIOGRAPHY␈↓ I6



␈↓ ↓H␈↓␈↓ ↓xINDEX␈↓ X